#include "BTreeNode.h"
#include <cassert>
#include <cmath>

using namespace std; 

BTLeafNode::BTLeafNode() {
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf) {

	if (pid < 0 || pid >= pf.endPid()) return RC_INVALID_PID;
	
	// read the page containing the leaf node
	RC rc;
	if ((rc = pf.read(pid, buffer)) < 0) return rc;
	
	return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf) {
	
	if (pid < 0 || pid > pf.endPid()) return RC_INVALID_PID;
	
	//write the page containing the leaf node
	RC rc;
	if ((rc = pf.write(pid, buffer)) < 0) return rc;
	
	return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount() { 
	return _BTGetNumKeys(buffer);
}

/*
 * Return the number of pointers stored in the node.
 * @return the number of pointers in the node
 */
int BTLeafNode::getPointerCount() {
	return _BTGetNumPointers(buffer);
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid, bool overflow) {
	if (!overflow) {
		if (getKeyCount() == BT_MAX_NUM_KEYS || getPointerCount() == BT_MAX_NUM_POINTERS)
			return RC_NODE_FULL;
	}
	else if (getKeyCount() == (BT_MAX_NUM_KEYS + BT_NUM_OVERFLOW_SLOTS)
				|| getPointerCount() == (BT_MAX_NUM_POINTERS + BT_NUM_OVERFLOW_SLOTS)) {
			return RC_NODE_FULL;
	}

	
	int numKeys = getKeyCount();
	int i = 0;
	for (; i < numKeys; i++) {
		int *k = getKey(buffer,i);
		if (*k > key) {
			break;
		}
		else if (*k == key) {
			//Duplicates not allowed.  Fail silently.
			return 0;
		}
	}
	
	//Insert the new key
	for (int j = numKeys-1; j >= i; j--) {
		int *keyPtr = getKey(buffer,j);
		memcpy(keyPtr+1, keyPtr, sizeof(int));
	}
	memcpy(getKey(buffer,i), &key, sizeof(int)); 
	
	for (int j = numKeys-1; j >= i; j--) {
		RecordId *ridPtr = getRecordId(buffer, j);
		memcpy(ridPtr+1, ridPtr, sizeof(RecordId));
	}
	memcpy(getRecordId(buffer, i), &rid, sizeof(RecordId));

	updateNumPointer(buffer, getPointerCount()+1);
	updateNumKey(buffer, numKeys+1);
	
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey) {

	if (sibling.getKeyCount() != 0 || sibling.getPointerCount() != 0)
		return RC_NONEMPTY_SIBLING;
	
	//The third parameter allows this insertion to overflow
	//the node.  We will fix the overflow before by splitting
	//the keys with the sibling.
	insert(key, rid, true);
	int numKey = getKeyCount();
	int numPtr = getPointerCount();
	int siblingIndex = (numKey % 2) ? numKey / 2 + 1 : numKey / 2;
	
	for (int j = siblingIndex; j < numKey; j++) {
		sibling.insert(*(getKey(buffer, j)), *(getRecordId(buffer, j)));
	}
	updateNumKey(buffer, siblingIndex);
	updateNumPointer(buffer, numPtr - numKey + siblingIndex);
	
	siblingKey = *(getKey(sibling.buffer, 0));
	
	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid) {
	int numKeys = getKeyCount();
	int i;
	int *key;
	for (i = 0; i < numKeys; i++) {
		key = getKey(buffer, i);
		if (*key >= searchKey) {
			eid = i;
			return 0;
		}
	}
	return RC_NO_SUCH_RECORD;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid) {
	if (eid >= getKeyCount() || eid < 0) {
		return RC_INVALID_CURSOR;
	}
	key = *(getKey(buffer, eid));
	rid = *(getRecordId(buffer, eid));
	
	return 0;
}

/*
 * Return the pid of the next sibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr() {
	RecordId *rid = (RecordId*)(buffer + BT_NEXT_NODE_PTR);
	return rid->pid;
}

/*
 * Set the pid of the next sibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid) {
	RecordId *rid = (RecordId*)(buffer + BT_NEXT_NODE_PTR);
	rid->pid = pid;
	if ( ! nextNodePtrIsSet() ) {
		updateNumPointer( buffer, getPointerCount() + 1 );
		_setNextNodePtrFlag();
	}
	return 0;
}

bool BTLeafNode::nextNodePtrIsSet() {
	return (buffer[0] & 0x01);
}

/*
 * Run some tests on BTLeafNode
 */
void BTLeafNode::test() {
	PageFile pf("bttest",'w');
	char buf[PageFile::PAGE_SIZE];
	PageId pid = pf.endPid();
	RecordId rid;
	RC rc;

    //Insert into an empty leaf node
	memset(buf, 0, PageFile::PAGE_SIZE);
	int numKeys = 0;
	int numPointers = 0;
	if (rc = pf.write(pid, buf)) {
		fprintf(stderr, "error: exited with status %d\n", rc);
		exit(1);
	}

	if (rc = read(pid, pf)) {
		fprintf(stderr, "error: exited with status %d\n", rc);
		exit(1);
	}

	assert(memcmp(buffer, buf, PageFile::PAGE_SIZE) == 0);
	assert(getKeyCount() == 0 && getPointerCount() == 0);
	rid.pid = 5;
	rid.sid = 6;
	insert(3,rid);
	write(pid, pf);
	memset(buffer, 0, PageFile::PAGE_SIZE);
	read(pid,pf);
	assert(getKeyCount() == 1 && getPointerCount() == 1);
	int *pkey = getKey(buffer,0);
	RecordId *prid = getRecordId(buffer,0);
	assert(*pkey == 3 && prid->pid == 5 && prid->sid == 6);

	//Insert a key less than all existing keys
	rid.pid = 10;
	rid.sid = 11;
	insert(0,rid);
	write(pid,pf);
	read(pid,pf);
	assert(getKeyCount() == 2 && getPointerCount() == 2);
	pkey = getKey(buffer,0);
	prid = getRecordId(buffer,0);
	assert(*pkey == 0 && prid->pid == 10 && prid->sid == 11);
	pkey = getKey(buffer,1);
	prid = getRecordId(buffer,1);
	assert(*pkey == 3 && prid->pid == 5 && prid->sid == 6);

	//Insert a key in the middle of the key values
	insert(1,rid);
	assert(getKeyCount() == 3 && getPointerCount() == 3);
	pkey = getKey(buffer,0);
	assert(*pkey == 0 && *(pkey+1) == 1 && *(pkey+2) == 3);

	//Fill the entire node
	memset(buffer,0,PageFile::PAGE_SIZE);
	for (int i = 0; i < BT_MAX_NUM_KEYS; i++) {
		insert(i,rid);
	}
	assert(getKeyCount() == BT_MAX_NUM_KEYS && getPointerCount() == BT_MAX_NUM_KEYS);
	prid = getRecordId(buffer,BT_MAX_NUM_POINTERS-1);
	assert(prid->pid == 0 && prid->sid == 0);

	//set next node pointer
	assert(!nextNodePtrIsSet());
	setNextNodePtr(-1);
	assert(getNextNodePtr() == -1);
	assert(getPointerCount() == BT_MAX_NUM_POINTERS);
	assert(nextNodePtrIsSet());

	//Insert into a full node
	assert(insert(BT_MAX_NUM_KEYS,rid) == RC_NODE_FULL);

	//Insert and Split: node is full, sibling gets the key
	BTLeafNode sibling;
	int siblingKey;
	memset(sibling.buffer, 0, PageFile::PAGE_SIZE);
    rid.pid = 100;
	rid.sid = 101;
	assert(insertAndSplit(BT_MAX_NUM_KEYS,rid,sibling,siblingKey) == 0);
	assert(getKeyCount() == 42);
	assert(sibling.getKeyCount() == 41);
	assert(siblingKey == 42);
	for (int i = 0; i < getKeyCount(); i++) {
		int* k = getKey(buffer,i);
		RecordId *r = getRecordId(buffer,i);
		assert(*k == i && r->pid == 10 && r->sid == 11);
	}
	for (int i = 0; i < sibling.getKeyCount() - 1; i++) {
		int *k = getKey(sibling.buffer, i);
		RecordId *r = getRecordId(sibling.buffer,i);
		assert(*k == getKeyCount() + i);
		assert(r->pid == 10 && r->sid == 11);
	}
	int *k = getKey(sibling.buffer,sibling.getKeyCount()-1);
	RecordId *r = getRecordId(sibling.buffer,sibling.getKeyCount()-1);
	assert(*k == BT_MAX_NUM_KEYS && r->pid == 100 && r->sid == 101);
	
	//nextNodePtr of the old node should be unchanged
	assert(getNextNodePtr() == -1);
	assert(sibling.getNextNodePtr() == 0);

	//Insert and Split: node is full, old node gets the key
	memset(buffer,0,PageFile::PAGE_SIZE);
	for (int i = 1; i < BT_MAX_NUM_KEYS+1; i++) {
		rid.pid = 10;
		rid.sid = 11;
		insert(i,rid);
	}
	memset(sibling.buffer, 0, PageFile::PAGE_SIZE);
	rid.pid = 100; rid.sid = 101;
	assert(insertAndSplit(0,rid,sibling,siblingKey) == 0);
	assert(getKeyCount() == 42);
	assert(sibling.getKeyCount() == 41);
	assert(siblingKey == 42);

	k = getKey(buffer,0);
	r = getRecordId(buffer,0);
	assert(*k == 0 && r->pid == 100 && r->sid == 101);
	for (int i = 1; i < getKeyCount(); i++) {
		k = getKey(buffer,i);
		r = getRecordId(buffer,i);
		assert(*k == i && r->pid == 10 && r->sid == 11);
	}
	for (int i = 0; i < sibling.getKeyCount(); i++) {
		k = getKey(sibling.buffer, i);
		r = getRecordId(sibling.buffer,i);
		assert(*k == getKeyCount() + i);
		assert(r->pid == 10 && r->sid == 11);
	}

	assert(getNextNodePtr() == 0);
	assert(sibling.getNextNodePtr() == 0);

	//Try to split with a non-empty sibling
	assert(insertAndSplit(0,rid,sibling,siblingKey) == RC_NONEMPTY_SIBLING);

	pf.close();
}

/********************************************************************
 *							BTNonLeafNode
*********************************************************************/

BTNonLeafNode::BTNonLeafNode() {
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf) {
	if (pid < 0 || pid >= pf.endPid()) return RC_INVALID_PID;
	
	// read the page containing the leaf node
	RC rc;
	if ((rc = pf.read(pid, buffer)) < 0) return rc;
	
	return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf){
	
	if (pid < 0 || pid > pf.endPid()) return RC_INVALID_PID;
	
	//write the page containing the leaf node
	RC rc;
	if ((rc = pf.write(pid, buffer)) < 0) return rc;
	
	return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount(){ 
	return _BTGetNumKeys(buffer);
}

/*
 * Return the number of pointers stored in the node.
 * @return the number of pointers in the node
 */
int BTNonLeafNode::getPointerCount() {
	return _BTGetNumPointers(buffer);
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid, bool overflow){
	if (!overflow) {
		if (getKeyCount() == BT_MAX_NUM_KEYS || getPointerCount() == BT_MAX_NUM_POINTERS)
			return RC_NODE_FULL;
	}
	else if (getKeyCount() == (BT_MAX_NUM_KEYS + BT_NUM_OVERFLOW_SLOTS) 
				|| getPointerCount() == (BT_MAX_NUM_POINTERS + BT_NUM_OVERFLOW_SLOTS)) {
		return RC_NODE_FULL;
	}
	int numKeys = getKeyCount();
	int i = 0;
	for (i; i < numKeys; i++) {
		int *k = getKey(buffer,i);
		if (*k > key)
			break;
		else if (*k == key) {
			//duplicates not allowed. fail silently
			return 0;
		}
	}
	
	//Insert the new key
	for (int j = numKeys-1; j >= i; j--) {
		int *keyPtr = getKey(buffer,j);
		memcpy(keyPtr+1, keyPtr, sizeof(int));
	}
	memcpy(getKey(buffer,i), &key, sizeof(int)); 
	
	int numPointers = getPointerCount();
	i += 1;
	for (int j = numPointers-1; j >= i; j--) {
		PageId *pidPtr = getPageId(buffer, j);
		memcpy(pidPtr+1, pidPtr, sizeof(PageId));
	}
	memcpy(getPageId(buffer, i), &pid, sizeof(PageId));
	
	updateNumPointer(buffer, numPointers+1);
	updateNumKey(buffer, numKeys+1);

	return 0;
}

RC BTNonLeafNode::insertLastPointer(PageId pid) {
	if (getPointerCount() == BT_MAX_NUM_POINTERS)
		return RC_NODE_FULL;
	if (getPointerCount() > getKeyCount())
		return RC_INVALID_LAST_POINTER;
		
	int pointerIndex = getPointerCount();
	memcpy(getPageId(buffer, pointerIndex), &pid, sizeof(PageId));
	updateNumPointer(buffer, pointerIndex+1);
	
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey){

	if (sibling.getKeyCount() != 0 || sibling.getPointerCount() != 0)
		return RC_NONEMPTY_SIBLING;//TODO, define this error
	
	insert(key, pid, true);
	int numKey = getKeyCount();
	int numPtr = getPointerCount();
	int midIndex = numKey / 2;
	midKey = *(getKey(buffer, midIndex));
	int siblingIndex = midIndex + 1;
	
	//needed to insert and split properly
	//getkey(buffer, siblingIndex) getPageId(buffer, siblingIndex)
	memcpy(getKey(sibling.buffer, 0) , getKey(buffer, siblingIndex), sizeof(int));
	updateNumKey(sibling.buffer, 1);
	memcpy(getPageId(sibling.buffer, 0), getPageId(buffer, siblingIndex), sizeof(PageId));
	updateNumPointer(sibling.buffer, 1);

	sibling.insertLastPointer(*getPageId(buffer, siblingIndex+1));

	for (int j = siblingIndex + 1; j < numKey; j++) {
		sibling.insert(*(getKey(buffer, j)), *(getPageId(buffer, j+1)), false);
	}
	
	updateNumKey(buffer, midIndex);
	updateNumPointer(buffer, midIndex+1);
		
	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid) {
	int numKeys = getKeyCount();
	int index;
	int *key;
	for (index = 0; index < getKeyCount(); index++) {
		key = getKey(buffer, index);
		if (*key > searchKey) {
			pid = *(getPageId(buffer, index));
			return 0;
		}
	}
		
	pid = *(getPageId(buffer, getPointerCount() -1));
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2) {
	updateNumKey(buffer, 1);
	updateNumPointer(buffer, 2);
	
	int *keyPtr = getKey(buffer, 0);
	memcpy(keyPtr, &key, sizeof(int));
	
	PageId *pageIdPtr = getPageId(buffer, 0);
	memcpy(pageIdPtr, &pid1, sizeof(PageId));
	
	pageIdPtr = getPageId(buffer, 1);
	memcpy(pageIdPtr, &pid2, sizeof(PageId));
	
	return 0;
}

RC BTNonLeafNode::readEntry(int eid, int& key, PageId& pid) {
	if (eid >= getKeyCount() || eid < 0) {
		return RC_INVALID_CURSOR;
	}
	key = *(getKey(buffer, eid));
	pid = *(getPageId(buffer, eid));
	
	return 0;
}

RC BTNonLeafNode::getLastNodePtr() {
	int last = getPointerCount() - 1;
	return *(getPageId(buffer, last));
}

RC BTNonLeafNode::test() {
	PageFile pf("btNonLeaftest", 'w');
	char buf[PageFile::PAGE_SIZE];
	PageId pid = pf.endPid();
	RC rc;
	
	memset(buf, 0, PageFile::PAGE_SIZE);
	int numKeys = 0;
	int numPointers = 0;
	if (rc = pf.write(pid, buf)) {
		fprintf(stderr, "error: exited with status %d\n", rc);
		exit(1);
	}

	if (rc = read(pid, pf)) {
		fprintf(stderr, "error: exited with status %d\n", rc);
		exit(1);
	}
	
	assert(memcmp(buffer, buf, PageFile::PAGE_SIZE) == 0);
	assert(getKeyCount() == 0 && getPointerCount() == 0);
	
	PageId p = 1;
	rc = initializeRoot(1, 3, 2);
	if (rc != 0) {
		fprintf(stderr, "error: exited with status %d\n", rc);
		exit(1);
	}
	write(pid, pf);
	memset(buffer, 0, PageFile::PAGE_SIZE);
	read(pid, pf);
	assert(getKeyCount() ==1 && getPointerCount() ==2);
	int *pkey = getKey(buffer, 0);
	PageId *page = getPageId(buffer, 0);
	assert(*pkey == 3 && *page == 1);
	
	//Insert Key less than existing keys
	rc = insert(1, 0);
	if (rc != 0) {
		fprintf(stderr, "error: exited with status %d\n", rc);
		exit(1);
	}
	write(pid, pf);
	read(pid, pf);
	assert(getKeyCount() == 2 && getPointerCount() == 3);
	pkey = getKey(buffer, 0);
	page = getPageId(buffer, 1);
	assert(*pkey == 1 && *page == 0);
	pkey = getKey(buffer, 1);
	page = getPageId(buffer, 2);
	assert(*pkey == 3 && *page == 2);
	
	//Insert key in middle
	rc = insert(2, 2);
	assert(getKeyCount() == 3 && getPointerCount() == 4);
	pkey = getKey(buffer, 0);
	page = getPageId(buffer, 1);
	assert(*pkey == 1 && *page == 0);
	pkey = getKey(buffer, 1);
	page = getPageId(buffer, 2);
	assert(*pkey == 2 && *page == 2);
	pkey = getKey(buffer, 2);
	page = getPageId(buffer, 3);
	assert(*pkey == 3 && *page == 2);
	
	//Fill up node
	memset(buffer, 0, PageFile::PAGE_SIZE);
	for (int i = 0; i < BT_MAX_NUM_KEYS; i++)
		insert(i, i % 4);
	
	//Insert last pointer
	assert(getKeyCount() == BT_MAX_NUM_KEYS && getPointerCount() == BT_MAX_NUM_KEYS);
	insertLastPointer(5);
	page = getPageId(buffer, BT_MAX_NUM_POINTERS-1);
	assert(getKeyCount() == BT_MAX_NUM_KEYS && getPointerCount() == BT_MAX_NUM_POINTERS && *page == 5);
	
	//Make sure unable to insert full node
	rc = insert(10, 10);
	assert(rc == RC_NODE_FULL);
	
	BTNonLeafNode sibling;
	int midKey = 0;
	insertAndSplit(82, 4, sibling, midKey);
	page = getPageId(buffer, getKeyCount());
	assert(getKeyCount() == 41 && getPointerCount() == 42 && midKey == 41);//original
	page = getPageId(sibling.buffer, 0);
	pkey = getKey(sibling.buffer, 0);
	assert(*pkey == 42 && sibling.getKeyCount() == 41 && getPointerCount() == 42);//sibling
	page = getPageId(sibling.buffer, sibling.getKeyCount() - 1);
	pkey = getKey(sibling.buffer, sibling.getKeyCount() - 1);	
	assert(*pkey == 82);
	page = getPageId(sibling.buffer, sibling.getKeyCount());

	memset(buffer, 0, PageFile::PAGE_SIZE);
	memset(sibling.buffer, 0, PageFile::PAGE_SIZE);
	for (int i = 2; i < BT_MAX_NUM_KEYS; i++)
		insert(i, i+1);
	insertLastPointer(100);
	insertAndSplit(85, 4, sibling, midKey);
	
	page = getPageId(sibling.buffer, sibling.getKeyCount());
	assert(*page == 4);
	assert(*getPageId(buffer, 0) == 0 && *getPageId(buffer, 1) == 3);
	
	locateChildPtr(40, *page);
	assert(*page == 41);
	
	locateChildPtr(1, *page);
	assert(*page == 0);
	
}
